package week6.Chapter6_列表.seatwork;

import week6.Chapter6_列表.jsjf.LinearNode;
import week6.Chapter6_列表.jsjf.ListADT;
import week6.Chapter6_列表.jsjf.exceptions.ElementNotFoundException;
import week6.Chapter6_列表.jsjf.exceptions.EmptyCollectionException;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * LinkedList represents a linked implementation of a list.
 *
 * @author Lewis and Chase
 * @version 4.0
 */
public abstract class LinkedList<T> implements ListADT<T>, Iterable<T>
{
    protected int count;
    protected LinearNode<T> head, tail;
    protected int modCount;

    /**
     * Creates an empty list.
     */
    public LinkedList()
    {
        count = 0;
        head = tail = null;
        modCount = 0;
    }

    /**
     * Removes the first element in this list and returns a reference
     * to it. Throws an EmptyCollectionException if the list is empty.
     *
     * @return a reference to the first element of this list
     * @throws EmptyCollectionException if the list is empty
     */
    @Override
    public T removeFirst() throws EmptyCollectionException
    {
        // To be completed as a Programming Project
        if (isEmpty()) {
            throw new EmptyCollectionException("LinkedList");
        }
        T result = head.getElement();
        head = head.getNext();
        count--;
        modCount++;
        return result;
    }

    /**
     * Removes the last element in this list and returns a reference
     * to it. Throws an EmptyCollectionException if the list is empty.
     *
     * @return the last element in this list
     * @throws EmptyCollectionException if the list is empty
     */
    @Override
    public T removeLast() throws EmptyCollectionException
    {
        // To be completed as a Programming Project
        if (isEmpty()) {
            throw new EmptyCollectionException("LinkedList");
        }
        LinearNode<T> temp = head;
        T result = temp.getElement();
        while (temp.getNext().getElement()!= tail.getElement()){
            temp = temp.getNext();
        }
        count--;
        modCount++;
        return result;
    }

    /**
     * Removes the first instance of the specified element from this
     * list and returns a reference to it. Throws an EmptyCollectionException
     * if the list is empty. Throws a ElementNotFoundException if the
     * specified element is not found in the list.
     *
     * @param  targetElement the element to be removed from the list
     * @return a reference to the removed element
     * @throws EmptyCollectionException if the list is empty
     * @throws ElementNotFoundException if the target element is not found
     */
    @Override
    public T remove(T targetElement) throws EmptyCollectionException, ElementNotFoundException
    {
        if (isEmpty()) {
            throw new EmptyCollectionException("LinkedList");
        }
        boolean found = false;
        LinearNode<T> previous = null;
        LinearNode<T> current = head;

        while (current != null && !found) {
            if (targetElement.equals(current.getElement())) {
                found = true;
            }
            else
            {
                previous = current;
                current = current.getNext();
            }
        }

        if (!found) {
            throw new ElementNotFoundException("LinkedList");
        }

        if (size() == 1)  // only one element in the list
        {
            head = tail = null;
        }
        else
        if (current.equals(head))// target is at the head
        {
            head = current.getNext();
        }
        else
        if (current.equals(tail))  // target is at the tail
        {
            tail = previous;
            tail.setNext(null);
        }
        else
        // target is in the middle
        {
            previous.setNext(current.getNext());
        }

        count--;
        modCount++;

        return current.getElement();
    }

    /**
     * Returns the first element in this list without removing it.
     *
     * @return the first element in this list
     * @throws EmptyCollectionException if the list is empty
     */
    @Override
    public T first() throws EmptyCollectionException
    {
        // To be completed as a Programming Project
        if (isEmpty()){
            throw new EmptyCollectionException("LinkedList");
        }
        else {
            T result = head.getElement();
            return result;
        }
    }

    /**
     * Returns the last element in this list without removing it.
     *
     * @return the last element in this list
     * @throws EmptyCollectionException if the list is empty
     */
    @Override
    public T last() throws EmptyCollectionException
    {
        // To be completed as a Programming Project
        if (isEmpty()){
            throw new EmptyCollectionException("LinkedList");
        }
        LinearNode<T> temp = head;
        while (temp.getNext()!=tail){
            temp = temp.getNext();
        }
        tail = temp;
        return temp.getElement();
    }

//    public void find_index(int index){
//
//    }
    /**
     * Returns true if the specified element is found in this list and
     * false otherwise. Throws an EmptyCollectionException if the list
     * is empty.
     *
     * @param  targetElement the element that is sought in the list
     * @return true if the element is found in this list
     * @throws EmptyCollectionException if the list is empty
     */
    @Override
    public boolean contains(T targetElement) throws EmptyCollectionException
    {
        // To be completed as a Programming Project
        if (isEmpty()) {
            throw new EmptyCollectionException("LinkedList");
        }
        boolean found = false;
        LinearNode<T> previous = null;
        LinearNode<T> current = head;

        while (current != null && !found) {
            if (targetElement.equals(current.getElement())) {
                found = true;
            }
            else
            {
                previous = current;
                current = current.getNext();
            }
        }

        if (!found) {
            throw new ElementNotFoundException("LinkedList");
        }

        if (size() == 1&&targetElement.equals(head.getElement()))
        {
            return true;
        }
        else
            if (current.getElement().equals(head.getElement()))
        {
            return true;
        }
        else
        if (current.getElement().equals(tail.getElement()))
        {
            return true;
        }
        else
        // target is in the middle
        {
            return false;
        }
    }

    /**
     * Returns true if this list is empty and false otherwise.
     *
     * @return true if the list is empty, false otherwise
     */
    @Override
    public boolean isEmpty()
    {
        // To be completed as a Programming Project
        if (count==0){
            return true;
        }
        else {
            return false;
        }
    }

    /**
     * Returns the number of elements in this list.
     *
     * @return the number of elements in the list
     */
    @Override
    public int size()
    {
//         To be completed as a Programming Project
//        LinearNode temp = head;
//        int count = 0;
//        while(temp.getNext() != null){
//            count++;
//            temp = temp.getNext();
//        }
        return count;
    }

    /**
     * Returns a string representation of this list.
     *
     * @return a string representation of the list
     */
    @Override
    public String toString()
    {
        // To be completed as a Programming Project
        String result = "";
        LinearNode node = head;
        for (int i = 0 ; i < size(); i++){
            result +=  node.getElement() + " ";
            node = node.getNext();
        }
        return result;
    }

    /**
     * Returns an iterator for the elements in this list.
     *
     * @return an iterator over the elements of the list
     */
    @Override
    public Iterator<T> iterator()
    {
        return new LinkedListIterator();
    }

    /**
     * LinkedIterator represents an iterator for a linked list of linear nodes.
     */
    private class LinkedListIterator implements Iterator<T>
    {
        private int iteratorModCount;  // the number of elements in the collection
        private LinearNode<T> current;  // the current position

        /**
         * Sets up this iterator using the specified items.
         *
         * @paramcollection  the collection the iterator will move over
         * @paramsize        the integer size of the collection
         */
        public LinkedListIterator()
        {
            current = head;
            iteratorModCount = modCount;
        }

        /**
         * Returns true if this iterator has at least one more element
         * to deliver in the iteration.
         *
         * @return  true if this iterator has at least one more element to deliver
         *          in the iteration
         * @throws  ConcurrentModificationException if the collection has changed
         *          while the iterator is in use
         */
        @Override
        public boolean hasNext() throws ConcurrentModificationException
        {
            if (iteratorModCount != modCount) {
                throw new ConcurrentModificationException();
            }

            return (current != null);
        }

        /**
         * Returns the next element in the iteration. If there are no
         * more elements in this iteration, a NoSuchElementException is
         * thrown.
         *
         * @return the next element in the iteration
         * @throws NoSuchElementException if the iterator is empty
         */
        @Override
        public T next() throws ConcurrentModificationException
        {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            T result = current.getElement();
            current = current.getNext();
            return result;
        }

        /**
         * The remove operation is not supported.
         *
         * @throws UnsupportedOperationException if the remove operation is called
         */
        @Override
        public void remove() throws UnsupportedOperationException
        {
            throw new UnsupportedOperationException();
        }
    }
}


